//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//
// 算法的时间复杂度应该为 O(log (m+n)) 。
//
//
//
// 示例 1：
//
//
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
//
//
// 示例 2：
//
//
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
//
//
//
//
//
//
// 提示：
//
//
// nums1.length == m
// nums2.length == n
// 0 <= m <= 1000
// 0 <= n <= 1000
// 1 <= m + n <= 2000
// -10⁶ <= nums1[i], nums2[i] <= 10⁶
//
// Related Topics 数组 二分查找 分治 👍 5552 👎 0

package leetcode.editor.cn;

import leetcode.editor.cn.utils.ArrayUtil;

class 寻找两个正序数组的中位数 {
    public static void main(String[] args) {
        //int[] arr1 = Arrays.stream(ArrayUtil.generateAbsoluteRandomArray(2, 100)).sorted().toArray();
        //int[] arr2 = Arrays.stream(ArrayUtil.generateAbsoluteRandomArray(2, 100)).sorted().toArray();
        int arr1[] = new int[]{};
        int arr2[] = new int[]{2, 3};
        ArrayUtil.printArray(arr1);
        ArrayUtil.printArray(arr2);

        Solution solution = new 寻找两个正序数组的中位数().new Solution();
        double rst = solution.findMedianSortedArrays(arr1, arr2);
        System.out.println(rst);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            if (nums1 == null || nums2 == null) {
                return -1;
            }
            int K = ((nums1.length + nums2.length) / 2) + 1;
            int[] merge = merge(nums1, nums2, K);
            return ((nums1.length + nums2.length) & 1) == 1 ? merge[K - 1] : (merge[K - 1] + merge[K - 2]) / 2D;
        }

        private int[] merge(int[] nums1, int[] nums2, int k) {
            int[] merged = new int[k];
            int l1 = 0, l2 = 0;
            for (int i = 0; i < k; i++) {
                if (l1 >= nums1.length) {
                    merged[i] = nums2[l2];
                    l2++;
                    continue;
                }
                if (l2 >= nums2.length) {
                    merged[i] = nums1[l1];
                    l1++;
                    continue;
                }
                if (nums1[l1] < nums2[l2]) {
                    merged[i] = nums1[l1];
                    l1++;
                } else {
                    merged[i] = nums2[l2];
                    l2++;
                }
            }
            return merged;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
